package day_7_12;

import java.util.HashMap;
import java.util.Map;

public class Main2 {
    /**
     *
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    // dfs + 前缀和，进行优化
    Map<Long,Integer> hash = new HashMap<>();

    public int pathSum(TreeNode root, int targetSum) {
        hash.put(0L,1); // 进行初始化，前缀和为0的值，是1次
        int ret = dfs(root,targetSum,0L);
        return ret;
    }
    // 相当于是 记忆化搜索。直接获取对应的值，不需要进行枚举
    public int dfs(TreeNode root,int targetSum,long curSum) {
        if(root == null) {
            return 0;
        }
        int ret = 0;
        curSum += root.val;
        ret = hash.getOrDefault(curSum - targetSum,0);
        hash.put(curSum,hash.getOrDefault(curSum,0) + 1);
        ret += dfs(root.left,targetSum,curSum);
        ret += dfs(root.right,targetSum,curSum);
        // 回溯
        hash.put(curSum,hash.getOrDefault(curSum,0) - 1);

        return ret;
    }

    // dfs + 枚举
    int ret;
    public int pathSum(TreeNode root, long targetSum) {
        // 使每一个节点都为 路径的一个开始节点
        if(root == null) {
            return 0;
        }

        dfs(root,targetSum);
        pathSum(root.left,targetSum);
        pathSum(root.right,targetSum);
        return ret;
    }

    public void dfs(TreeNode root,long targetSum) {
        if(root == null) {
            return;
        }
        int val = root.val;
        if(targetSum == val) {
            ret++;
        }

        dfs(root.left,targetSum - val);
        dfs(root.right,targetSum - val);
    }
}
